template <class Type>
DetFinAut<Type>::DetFinAut()
{
}

template <class Type>
DetFinAut<Type>::DetFinAut(Type start, list<Type> &finishList)
{
	this->start = start;
	this->finishList = finishList;
}

template <class Type>
DetFinAut<Type>::~DetFinAut()
{
}

template <class Type>
bool DetFinAut<Type>::accept(string symbols)
{
	bool check;
	Type begin;
	Type last;
	list<Type>::const_iterator i, l;
	list<Transition<Type>>::const_iterator k;	
		check = true;
		begin = start;
		for(unsigned int j = 0; j < symbols.length(); j++)
		{
			for(k = this->transitionList.begin(); k != this->transitionList.end(); k++)
			{
				if(k->begin == begin && k->symbol == symbols[j])
				{
					begin = k->end;
					last = k->begin;
					break;
				}
			}
			if(k == this->transitionList.end())
			{
				check = false;
				break;
			}
		}
		if(check)
		{
			for(l = this->finishList.begin(); l != finishList.end(); l++)
			{
				for(k = this->transitionList.begin(); k != this->transitionList.end(); k++)
				{
					if(k->begin == last && k->symbol == symbols[symbols.length() -1] && k->end == *l)
					{
						return true;
					}
				}
			}
		}
	
	return false;
}

template <class Type>
void DetFinAut<Type>::addTransition(Type begin, char symbol, Type end)
{
	Transition<Type> transition;
	this->stateList.push_front(begin);
	this->symbolList.push_front(symbol);
	this->stateList.push_front(end);
	stateList.sort();
	stateList.unique();
	symbolList.sort();
	symbolList.unique();
	transition.begin = begin;
	transition.symbol = symbol;
	transition.end = end;
	this->transitionList.push_back(transition);
}

template <class Type>
list<string> DetFinAut<Type>::getLanguage(int size)
{
	list<string> resultList;
	list<Type>::const_iterator i;
	list<Transition<Type>>::const_iterator j;
	for(i = this->finishList.begin(); i != this->finishList.end(); i++)
	{
		if(*i == this->start)
		{
			resultList.push_front("");
		}
	}
	if(size >= 1)
	{
		for(j = this->transitionList.begin(); j != this->transitionList.end(); j++)
		{
			if(j->begin == this->start)
			{
				DetFinAut<Type> detFinAut = DetFinAut<Type>(j->end, this->finishList);
				list<string> tempList;
				list<string>::const_iterator k;
				detFinAut.transitionList = this->transitionList;
				tempList = detFinAut.getLanguage(size - 1);
				for(k = tempList.begin(); k != tempList.end(); k++)
				{
					resultList.push_back(j->symbol + *k);
				}
			}
		}
	}
	return sort(resultList);
}

template <class Type>
void DetFinAut<Type>::printTransitionRules()
{
	list<Type>::const_iterator i;
	list<char>::const_iterator j;
	list<Transition<Type>>::const_iterator k;
	cout << "5-Tupel    :    M = ( {"; 
	for(i = stateList.begin(); i != stateList.end(); i++)
	{
		if(i == (stateList.end()))
		{
			cout << *i;
		}
		else
		{
			cout << *i << ", ";	
		}
	}
	cout << "}, {";

	for(j = symbolList.begin(); j != symbolList.end(); j++)
	{
		if(j == symbolList.end())
		{
			cout << *j;
		}
		else 
		{
		cout << *j << ", ";
		}
	}
	cout << "}, {";
	cout << this->start;
	cout << "}, {";

	for(i = finishList.begin(); i != finishList.end(); i++)
	{
		if(i == finishList.end())
		{
			cout << *i;
		}
		else
		{
			cout << *i << ",";               
		}
	}
	cout << "} )" <<endl<<endl;

	for(k = transitionList.begin(); k != transitionList.end(); k++)
	{
		string transition;
		transition += k->begin;
		transition += " >- ";
		transition += k->symbol;
		transition += " -> ";
		transition += k->end;
		if(k == transitionList.begin())
		{
			cout << "transitions:    " << transition << endl;
		}
		else
		{
			cout << "                " << transition << endl;
		}
	}
}


template <class Type>
void DetFinAut<Type>::print(int count)
{
	list<string> tempList;
	list<string>::const_iterator l;
	
	cout << endl;
	
	cout << endl;
	
	
	
	cout << endl;
	tempList = getLanguage(count);
	for(l = tempList.begin(); l != tempList.end(); l++)
	{
		if(l == tempList.begin())
		{
			cout << "language:       " << "[" << *l << "]" << endl;
		}
		else
		{
			cout << "                " << "[" << *l << "]" << endl;
		}
	}
}

template <class Type>
list<string> DetFinAut<Type>::sort(list<string> &sourceList)
{
	list<string> resultList;
	list<string>::const_iterator i, j;
	for(i = sourceList.begin(); i != sourceList.end(); i++)
	{
		if(resultList.empty())
		{
			resultList.push_front(*i);
		}
		else
		{
			for(j = resultList.begin(); j != resultList.end(); j++)
			{
				if(j->length() > i->length())
				{
					break;
				}
			}
			resultList.insert(j, *i);
		}
	}
	return resultList;
}

template<class Type>
list<char> DetFinAut<Type>::getSymbolList()
{
	return symbolList;
}

template<class Type>
list<Type> DetFinAut<Type>::getStateList()
{
	return stateList;
}

template<class Type>
list<Type> DetFinAut<Type>::getFinishList()
{
	return finishList;
}

template<class Type>
list<Transition<Type> > DetFinAut<Type>::getTransitionList()
{
	return transitionList;
}

template<class Type>
bool DetFinAut<Type>::isEndState(const Type &state)
{
	for(list<Type>::const_iterator iter = finishList.begin(); iter != finishList.end(); iter++)
	{
		if(*iter == state)
		{
			return true;
		}
	}
	return false;
}

template<class Type>
Type DetFinAut<Type>::getStart()
{
	return start;
}

template<class Type>
void DetFinAut<Type>::setStart(const Type &start)
{
	this->start = start;
}

template<class Type>
void DetFinAut<Type>::addFinishState(const Type &string)
{
	this->finishList.push_front(string);
}

template <class Type>
void DetFinAut<Type>::makeDrawning(DetFinAut<Type> &obj)
{
	list<Transition<Type>> objTable = obj.getTransitionList();
	list<Transition<Type>>::iterator itObj;
	Type start = obj.getStart();
	list<Type> StartStates;
	StartStates.push_back(start);
    list<Type>::iterator itStartStates;
	list<Type> EndStates = obj.getFinishList();
    list<Type>::iterator itEndStates;
    //string ErrorState = obj.getErrorState();
    ofstream myfile;
    myfile.open ("drawing");
    myfile << "digraph G { \n";
    bool combinedStartEnd=false;

    for (itEndStates=EndStates.begin(); itEndStates!=EndStates.end(); itEndStates++)
        myfile << *itEndStates << "[color=yellow style=filled]; \n";
//    if(ErrorState.length()>1)
  //      myfile << ErrorState << "[color=red style=filled]; \n";

    //kleuren van start/stop en error-states
    for (itStartStates=StartStates.begin(); itStartStates!=StartStates.end(); itStartStates++)
    {
		bool isEndState=false;
        for (itEndStates=EndStates.begin(); itEndStates!=EndStates.end(); itEndStates++)
        {
			if(*itStartStates==*itEndStates)
            {
                    //EndStates.erase(*itEndStates);
                    combinedStartEnd=true;
                    isEndState=true;
                    myfile << *itStartStates << "[color=green style=filled]; \n";
                    break;
            }

        }
            if(!isEndState)
                myfile << *itStartStates << "[color=blue style=filled]; \n";
    }


    //schrijven legenda!
	if(StartStates.size() >1)
        if(combinedStartEnd)
            myfile << "StartEndStates [shape = box color=green style=filled]; \n";
        else
            myfile << "StartStates [shape = box color=blue style=filled]; \n";
    
        if(combinedStartEnd)
            myfile << "StartEndState [shape = box color=green style=filled]; \n";
        else
            myfile << "StartState [shape = box color=blue style=filled]; \n";
    if(EndStates.size()>1)
        myfile << "EndStates [shape = box color=yellow style=filled]; \n";
    else
        if(EndStates.size()==1)
            myfile << "EndState [shape = box color=yellow style=filled]; \n";
//    if(ErrorState.length()>1)
  //      myfile << "ErrorState [shape = box color=red style=filled]; \n";

    //schrijven states en transities
    for (itObj=objTable.begin(); itObj!=objTable.end(); itObj++)
		myfile << (*itObj).begin << "->" << (*itObj).end << "[taillabel=\"" << (*itObj).symbol << "\"]; \n";

    myfile << "} \n";
    myfile.close();
    //aanmaken drawing.png d.m.v. command line util
    system("dot -Kdot -Tpng -O drawing");
    //gebruik windows geregistreerde viewer voor png bestanden
    system("drawing.png");
}

